package lhc.alg.top100;

/**
 * description: https://leetcode.cn/problems/flatten-binary-tree-to-linked-list/
 *  二叉树展开成链表 递归 平铺开拼接
 * author: hongchen.liao
 * date:  2022/8/15
 */
public class _114_Flatten_Binary_Tree_to_Linked_List {


      //Definition for a binary tree node.
      public class TreeNode {
          int val;
          TreeNode left;
          TreeNode right;
          TreeNode() {}
          TreeNode(int val) { this.val = val; }
          TreeNode(int val, TreeNode left, TreeNode right) {
              this.val = val;
              this.left = left;
              this.right = right;
          }
      }

    class Solution {
        public void flatten(TreeNode root) {
            if(root == null){
                return;
            }
            //左子树展开为链表
            flatten(root.left);
            //右子树展开为链表
            flatten(root.right);
            //把左子树拼接到右子树中
            TreeNode node = root.left;
            if(node != null){
                //找到左子树中的右尾节点
                while(node.right != null){
                    node = node.right;
                }
                //把右子树拼接到左子树尾节点的右边
                node.right = root.right;
                //把左子树拼接到右节点
                root.right = root.left;
                root.left = null;
            }
        }
    }


}
